L'automate (d'après BAC ES, Amérique du Nord 2019)

Énoncé

Pour accéder à un local d'une petite entreprise, les employés doivent choisir un code reconnu par l'automate suivant :

Une succession de lettres constitue un code possible si ces lettres se succèdent sur un chemin du graphe orienté ci-dessus, en partant du sommet n° 1 et en sortant au sommet n° 4.

Par exemple :

• le mot  \(bcbab\)  est un mot reconnu par cet automate, et correspond au chemin  \(121334\)  ;
• le mot  \(abac\)  n'est pas reconnu par cet automate.

1. Parmi les mots \(abab, abc, abbcbb\) , quels sont ceux qui sont reconnus par cet automate ?

2. Écrire la matrice d'adjacence \(A\)  du graphe, en rangeant les sommets dans l'ordre croissant.

3. Quel est le nombre minimal de lettres d'un code possible ? Justifier.

4. Y a-t-il un nombre maximal de lettres d'un code possible ? Justifier.

5. On a calculé  \(A^4=\begin{pmatrix}5&3&10&5\\1&6&7&4\\1&3&4&2\\2&1&4&2\end{pmatrix}\)  et  \(A^5=\begin{pmatrix}3&15&18&10\\6&6&14&7\\3&4&8&4\\1&6&7&4\end{pmatrix}\) .

    a. Combien y a-t-il de mots de quatre lettres qui conviennent ? Quels sont-ils ?
    b.  Combien y a-t-il de mots de cinq lettres qui conviennent ?
    c. Pour varier les mots possibles, l'un des employés suggère de changer la programmation de l'automate pour utiliser dorénavant les chemins qui entrent au sommet n° 1 et sortent au sommet n° 2. Est-ce une bonne idée avec des mots de quatre lettres ? Avec des mots de deux lettres ?